from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-26. 删除有序数组中的重复项
    给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
    然后返回 nums 中唯一元素的个数。

    考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
    更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
    返回 k 。
    """

    def removeDuplicates(self, nums: List[int]) -> int:
        """
        :param nums:
        :return:
        解题失败的原因：题目理解有问题！！！
        1、非严格递增排列，数组还是有序的从小到大排序的数据！
        2、“请你 原地 删除重复出现的元素，使每个元素 只出现一次”，删除重复的，但是曾经重复的需要出现一次！！
        """
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
        return k

    def removeDuplicates_20250724(self, nums: List[int]) -> int:
        """
        :param nums:
        :return:
        解题思路：
        双指针
        左指针指向：需要跟右指针去比对是否会重复的值。左指针之前的值，都是已经判断过不会重复的值
        """
        left = 0
        right = 1
        while right < len(nums):
            if nums[left] != nums[right]:
                nums[left + 1] = nums[
                    right]  # 很重要，如果不相等，则把右指针的值赋值给左指针的后一位，然后左指针加1，左指针就指向了一个【需要跟后面的比较，来判断后面的是否会跟左指针执行的值重复】
                left += 1
                right += 1
            else:
                right += 1
        return left + 1

    def removeDuplicates_review_20250729(self, nums: List[int]) -> int:
        """
        解题思路：
        ！！！注意：前提，数组是有序数组；需要原地删除，用指针控制下标，去更新对应下标里面的元素
        左右指针控制，左指针对应的是检测过，不重复的值的下标，右指针，对应的是待检测的值
        """
        left = 0
        right = 1
        while right < len(nums):
            if nums[left] != nums[right]:
                left += 1
                nums[left] = nums[right]  # ！！！注意这里要注意把有效的不重复值赋值一下
            right += 1
        return left + 1  # ！！！注意这里要+1，因为left对应的是下标，需要返回的是list长度，所以要+1


if __name__ == '__main__':
    s = Solution()

    # nums = [1, 1, 2]
    nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    # k = s.removeDuplicates(nums)
    k = s.removeDuplicates_20250724(nums)
    # k = s.removeDuplicates_review_20250729(nums)
    print('k:', k, 'nums:', nums)
